For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
1answer
25 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
1
vote
2answers
23 views

How many possible orders are there?

A tapas bar serves 15 dishes, of which 7 are vegetarian, 4 are fish and 4 are meat. A table of customers decides to order 8 dishes, possibly including repetitions. a)Calculate the number of possible ...
0
votes
0answers
14 views

What's the approximation of such a combination? [duplicate]

Given $k,m, k \leq m$. $N=\binom {m+k}{m}$ What's the approximation of N?
6
votes
0answers
29 views

In how many ways can the integers from $1$ to $n$ be divided into two groups with the same sum?

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum? I have tried calculating some of these values for small $n$, but cannot seem to find a pattern. Any ...
2
votes
0answers
17 views

Combinatorics: number of functions/predicates satisfying a sum on their entries

Given integers $n,m$, is there a closed form expression for the cardinality of the following set? $$\left\{ p : \{1,\dots,n\}^2 \rightarrow \{true,false\} \quad \Bigg| \sum_{i,j,k \in \{1,\dots,n\}} ...
0
votes
2answers
18 views

Counting problem: ways of opening stores in non-adjacent blocks?

A coffee company wants to set up stores along the main street of town, which has $n$ blocks. The company won’t open two stores in the same block, or in two adjacent blocks. Q: For this coffee shop, ...
1
vote
0answers
26 views

Combinatorial formula for the number of different words

Does there exist a closed formula for the following: Suppose we have $m$ distinct letters and we are allowed to use each letter at most $d$ times. What is the number of distinct words of length $k?$ ...
1
vote
1answer
29 views

How can I find how many unique strings there are with an equal numbers of elements, given a string length and number of elements to choose from?

The question is all in the title. Here's an example: Elements: A, B; Length: 4: AABB ABAB ABBA BABA BBAA BAAB There are 6 such unique strings for 2 elements and ...
0
votes
0answers
18 views

Maximizing the following function

I need to find values of $k_1$, $k_2$ and $k_3$ that maximize $C^{m_1}_{mm_1} \cdot C^{m_2}_{k_1-mm_1} \cdot C^{n_1}_{nn_1} \cdot C^{n_2}_{k_2-nn_1} \cdot C^{p_1}_{pp_1} \cdot C^{p_2}_{k_3-pp_1}$ ...
1
vote
1answer
18 views

The generating set of Cayley graphs over $Z_n$

Say we have a undirected and connected Cayley graph over $\mathbb{Z}_n$, with generating set $S=\{\pm x_0,\pm x_1,\ldots,\pm x_k\}$. Is it true that we can assume without the loss of generality that ...
6
votes
1answer
109 views

Proof of an identity of $n!$

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is: \begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n ...
0
votes
4answers
43 views

How many three digit numbers with increasing digits can be formed from the set $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

Suppose we pick 3 numbers $x,y,z \in \{1,2,3,4,5,6,7,8\}$ and form a 3 digit number $xyz$ how many possible combinations numbers can we create such that $x < y < z$. For example $357$ ...
0
votes
3answers
40 views

Probability of choosing two numbers so they differ by at least 2

A box has $10$ balls numbered $1,2, \dots, 10.$ A ball is picked at random and then a second ball is picked at random from the remaining nine balls. Find the probability that the numbers on the two ...
2
votes
3answers
60 views

Two dice thrown together.

Each face of a die is marked with a different number from 1 to 6. The number on the faces of the die are marked in such a way that the sum of the numbers on any pair of opposite faces is 7. Two such ...
0
votes
0answers
18 views

Number of subset problem [duplicate]

Question: A woman is preparing to go for a party .She need to colour her nails (all her nails considered 10 nails) She want to use either pink nail polish or red nail polish to colour each nails. ...
3
votes
2answers
61 views

Set and subsets link by prime numbers

I have a bit idea to solve this problem for small $n$ by programation but I think for $n>100$ I will need maths to help me. My problem is : Let S be the set of prime numbers less than n. Find ...
5
votes
1answer
57 views

How to prove the maximum possible number of elements of $S$ is $48$?

Let set $S\subseteq \{1,2,3,\cdots,100\}$,for any two different $a,b\in S$,there exist postive integer $k$ and $c,d\in S(c<d)$,($c,d$ can equal to $a$ or $b$),such $$a+b=c^k\cdot d$$ show that ...
-6
votes
2answers
50 views

Chances of this… [on hold]

9 people sat in a circle. They wrote their name on a piece of paper, folded it over and placed it in a hat. The hat was shuffled to mix up the pieces of paper. The first person picked out the name ...
1
vote
1answer
16 views

Number of solutions to equation $\sum_{i=1}^{n}x_i = R$ where $x_i>k$ where $k$ is a positive number

I know that the number of solutions to an equation of the form: $$\sum_{i=1}^{n}x_i = R$$ equals $\binom{n+R-1}{R}$. I am aware of the $x_i$ LESS THAN EQUAL TO case where, if say $x_6 \leq 3$, I ...
0
votes
2answers
46 views

In how many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty?

How many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty? So if I do this similar to stars and bars I am looking to put $n$ balls in actually $n-1$ urns, so ...
0
votes
1answer
34 views

Dividing $n$ identical things into $r$ groups

I was reading a course on Combinatorics where I came across following: The number of ways in which $n$ identical things can be divided into $r$ groups so that no group contains less than $m$ items ...
2
votes
3answers
35 views

Number of words which can be formed with INSTITUTION such that vowels and consonants are alternate

Question: How many words which can be formed with INSTITUTION such that vowels and consonants are alternate? My Attempt: There are total 11 letters in word INSTITUTION. The 6 consonants are ...
7
votes
3answers
157 views

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon and no vertice ...
2
votes
1answer
60 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
5
votes
3answers
421 views

How many possible words of this type can be formed?

We are making $10$ letter words using the letters $A,C,G,T$. How many possible words are there of the form $A...AC...CG...GT...T$ This is where all of the $A's$ go before the all of the $C's$ and ...
3
votes
0answers
50 views

Is it 3-D Catalan numbers?

I am studying Catalan numbers recently but I think that how about 3-D Catalan? So that I imagine following situation ; A man travel through the path-way parallel to $ x, y, z $ axis from O ...
2
votes
1answer
42 views

How many $10$ letter anagrams of KOLMOGOROV don't contain the subword GROOV?

How many $10$ letter anagrams of KOLMOGOROV don't contain the subword GROOV? Not sure how to do this one. Obviously there are $\frac{10!}{4!}$ anagrams of KOLMOGOROV but I'm not sure how to account ...
1
vote
0answers
34 views

A Combinational identity using permutations

For a distribution {$p_1,p_2, …,p_m$}, with $p_i>0$ and$\sum_1^m{p_i}=1$ , let $J$ be a subset of size $j$, and $m>j\geq1$. It holds that: $$\int_0^1\prod_{i \in J} (x^{-p_i}-1) dx = ...
0
votes
1answer
45 views

Chair arrangement problem - recurrence

Say we have $n$ chairs in a row. We will settle down $k$ guests on those chairs. It is not possible to settle down two people beside each other on two consecutive chairs. How many ways are there to ...
2
votes
3answers
43 views

Different ways of giving away 35 coins to 5 people?

The first part of the problem asks how many ways there are to give away 35 identical coins to 5 people, and I've concluded that it's ${35 \choose 5}$ because you're selecting how many ways you can ...
-4
votes
1answer
45 views

Solving $x+2y+3z=100$ in nonnegative integers. [on hold]

Solving for number of solution in set of non-negative integer of $$x+2y+3z=100$$ by generating function but finding problem in writing partial fraction of ...
0
votes
1answer
24 views

What's the least number of combinations you need to determine who the most efficient members are?

Not sure if this question fits here, but it's something I was thinking about last night. Maybe someone can throw some light on it. Let's say I have a group of people doing some shared task. Let's ...
2
votes
0answers
33 views

Counting Spanning Trees Needed to cover Edges

This is in the same spirit as this stackexchange post, but I am seeking a more general answer. The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed ...
-4
votes
1answer
29 views

Number of different possible armies in Clash of Clans [on hold]

Suppose we are given a set of sixteen different units. How many different armies of $200$ units exist ? In other words, how many $16$-uplets $(c_1, \cdots, c_{16})$ exist such that for each $i$, ...
1
vote
1answer
27 views

How many different ways can you choose a group of 4 people?

You have a total of 9 people to choose from. Of these 9 people you are supposed to create a group of 4. How many different ways can the new group look? This is my reasoning: To the new group, the ...
3
votes
1answer
24 views

Generating Constrained Random Distributions

I am trying to help another StackExchange user. We are attempting to fill a 6x6 matrix with 12 A's, 12 B's, and 12 C's subject to the constraint that each row contains 2 A, 2B and 2 C and each column ...
2
votes
1answer
26 views

How to answer this graph theory question?

Okay so let me define some terms before I ask my problem: Let $K_n$ denote the complete graph on $n$ vertices with $n\geq 2$ and let $C_3$ be a cycle of length $3$ (a triangle). Suppose $x,y,z$ ...
0
votes
0answers
51 views

Mega-straight flush with a huger hand

Three days ago I asked about the probability of drawing a straight flush when being dealt $26$ out of the $52$ cards of the deck, which Michael wisely solved. Now I'd like to make things more ...
1
vote
1answer
29 views

Combinatorial optimization problem

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem. If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can ...
0
votes
0answers
35 views

Computing an exponential generating function from the first few terms

The current question is related to this one, and this other one. I have a number sequence, and I want to find generating ...
0
votes
2answers
20 views

Partition set of $n$ elements until each partition contains $1$ element. Must terminate after exactly $n-1$ iterations?

Suppose I have a set of $n$ elements and I want to partition the set (split into two) until each partition contains a single element. How do I see that the terminating case must occur after exactly ...
1
vote
0answers
22 views

Is there a name for the relationship between matching combinations?

Is there a term that describes the relationship between $\binom 3 1 = \binom 3 2$ or $\binom 5 2 = \binom 5 3$? Symmetric comes to mind, but I was wondering if a specific term is used to describe ...
1
vote
1answer
19 views

A conjecture on binomial factors

Can any one help me prove the following conjecture: \begin{equation} \sum_{p=1}^{\min(n,m+1)}C_{m+1}^p C_{n-1}^{p-1}=\sum_{p=1}^{\min(m+1,n+1)}C_n^{p-1}C_m^{p-1}=C_{m+n}^n \end{equation} Here ...
2
votes
1answer
31 views

Counting the functions with f(i) ≤ f(i+1) for all i=1,..,n-1

How can I determine how many functions are weakly monotone increasing from $[n]\equiv \{1,..,n\}$ to itself: $$ f:[n] \to [n] \text{ so that } f(i) \leq f(i+1) \; \forall i\in[n-1]$$ Thank you for ...
4
votes
1answer
36 views

Variant Generating Function related to Euler Numbers

The generating function $$\frac{2e^x}{e^{2x}+1}=\sum_{n\ge 0}E_k\frac{x^k}{k!}$$ counts the number of alternating permutations of a set with an even number of elements. My question is this, if we ...
4
votes
2answers
38 views

Triangular Array's Recursive Formula Breakdown

I have the following polynomials: $$1$$ $$z-1$$ $$z^2-2z+3$$ $$z^3-3z^2+9z-15$$ $$z^4-4z^3+18z^2-60z+93$$ $$z^5-5z^4+30z^3-150z^2+465z-725$$ $$...$$ They are generated both recursively and explicitly. ...
1
vote
1answer
25 views

How many different towers, with regards to colour, can be built?

You are going to build a tower with coloured blocks. There are ten available blocks, of which three are white, two are red, two are yellow, one is green, one is blue and one is black. The tower you ...
0
votes
1answer
13 views

Which is the more likely outcome when dealing cards.

Suppose you are given 6 cards. Which is more likely, you get $3$ different value cards with value having $2$ suits. (e.g. two aces two kings and two jacks). Or $2$ different value cards with $3$ ...
2
votes
2answers
31 views

Number of ways to place $K$ objects in $N^3$ cube

On how many ways I can place $K$ objects in $N \times N \times N$ cube, assuming that in every coordinate $x$, $y$, $z$ (i.e. in every "row") may be at most one object? For example, if $N = 2$ and $K ...
1
vote
2answers
31 views

How many 3 letters-long codes can be made by 5 different letters?

You have five letters: C, H, E, S, T How many different codes, consisting of three letters, can be made from the above letters? I'd say ${5}\choose{3}$ is the correct answer, since the order of the ...