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)

1
vote
3answers
23 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 ...
0
votes
1answer
20 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 ...
4
votes
3answers
63 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$ dots, in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon. Intersection of the lines ...
4
votes
3answers
237 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 ...
2
votes
1answer
54 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
30 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 = ...
2
votes
1answer
41 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 ...
0
votes
0answers
37 views

Solve the following recurrence relation in two variables

How to solve this recurrence $$S(m,n)=S(m,n-1)+S(m-1,n-1)+S(m-1,n)$$ with base conditions $$S(1,1)=3,\; S(0,n)=S(m,0)=1.$$ This recurrence came up when I tried to solve this problem: Find the ...
0
votes
1answer
37 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 ...
3
votes
0answers
127 views

Elementary symmetrical polynomial equations, whose solutions are known to be natural numbers.

Let $n_1,n_2,\dots,n_k$ be natural numbers (excluding 0), and for each $1\leq i\leq k$ let $\sigma_i(n_1,n_2,\dots,n_k)$ be the elementary symmetrical polynomial consisting of the sum of all products ...
2
votes
3answers
37 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
42 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
4answers
59 views

Simplifying a fraction with binomial coefficients [closed]

I'm trying to do a simple combination but seem to forget the shortcut. It is $${\binom{6}{2}+\binom{4}{2} \over \binom{10}{2}}$$ Now finding the answer on my calculator is easy, the problem is that I ...
0
votes
1answer
23 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 ...
3
votes
2answers
30 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. ...
3
votes
1answer
22 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 ...
-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$, ...
2
votes
0answers
27 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 ...
0
votes
0answers
44 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
23 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 ...
2
votes
0answers
62 views
+50

The recurrence $a(n,k) = \sum_{0\leqslant j<n} a(n+j,k-1)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a(0,k) = 0, \quad \forall k\geqslant 1; \\ &a(1,k) = 1, \quad \forall k\geqslant 1; \\ ...
2
votes
1answer
21 views

Neighboring transpositions for number of length n, Kendall Tau Distance

I have the following question: Given is a string (or number) of length n, n being the number of its digits (or characters) - say for instance given is the number "12345" which has length n = 5. ...
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$ ...
1
vote
1answer
28 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
1answer
28 views

q-binomial Identity

Unfortunately I am not able to solve the following problem: I tried finding a bijection similar to the prove of this binomial identity: $$\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n-k}{m-k}$$ ...
0
votes
0answers
29 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
1answer
17 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 ...
4
votes
1answer
32 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 ...
0
votes
4answers
106 views

Number of certain (0,1)-matrices, Stanley's Enumerative Combinatorics

Stanley's Enumerative Combinatorics (http://www-math.mit.edu/~rstan/ec/ec1.pdf) contains next fact: 1.1.3 Example. Let f(n) be the number of n × n matrices M of $0$’s and $1$’s such that every row and ...
1
vote
7answers
183 views

How to show $\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$?

Show that $\,\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to ...
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 ...
2
votes
1answer
30 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 ...
1
vote
1answer
18 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 ...
0
votes
1answer
330 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
1
vote
0answers
36 views

Partitioning real numbers with sum $1$ to sets

If the sum of a finite number of positive real numbers is $1$ and each of them is less than $x$, then those real numbers can be partitioned into $50$ sets (some of which may be empty) such that the ...
3
votes
2answers
77 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...
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 ...
2
votes
2answers
30 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 ...
0
votes
0answers
52 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ A_x$ is the symmetric matrix of the graph $(G-x)$, where $C$ is the ...
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$ ...
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 ...
5
votes
5answers
615 views

Given $n \in \mathbb N$, prove $\sum^n_{k=0}(-1)^k {n \choose k} = 0$

I tried to solve it using induction, but that got me no were, in the middle of the equation stat appearing ks that I don't see how to get out of the equation. I think the easiest way to prove it, it's ...
2
votes
1answer
291 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
0
votes
2answers
31 views

Number of ways to assign $8$ subjects to $4$ people s.t. one gets an odd number of subjects

I am asked to find the number of ways to assign $8$ subjects to $4$ people, such that the third person always gets an odd number of subjects. What I did was consider the problem as putting ...
2
votes
0answers
44 views

Different coloured bottles of two different sizes

Question The table below shows the distribution by colour (green, blue and red) and size (small and large) of a collection of $20$ bottles. All other features of the bottles are exactly the same. ...
0
votes
0answers
26 views

Sum of products of K numbers taken from N numbers in closed form

Let's say i have 5 numbers, $A,B,C,D,E$. I want to know the sum of all the possible products of some or all of these numbers each taken at most once. Instead of a lot of multiplications and additions ...
4
votes
1answer
267 views

a combinatorial exercise

The problem asks us to calculate: $$ \sum_{i = 0}^{n}(-1)^i \binom{n}{i} \binom{n}{n-i}$$ The way I tried solving is: The given sum is the coefficient of $x^n$ in $ (1+x)^n(1-x)^n $, which is $ (1 ...
2
votes
1answer
35 views

What do we call well-founded posets whose elements have a unique height?

What do we call those well-founded posets $P$ with the property that for every $x \in P$, all maximal chains in the lowerset generated by $x$ have the same length? Examples: The set of all finite ...
0
votes
3answers
50 views

How to approach combinatorics proofs like these.

Okay so I have been trying to solve problems for my course and keep running into persistent issues with proofs. For example. Prove the following: $${n\choose r}={n-1\choose r-1}+{n-1\choose r}$$ ...